package puzzle.projecteuler.p200;





public class Problem159C {

	/**
	 * 注意：mdrs(n) = max { mdrs(n1) + mdrs(n2) | n = n1*n2, n1,n2 > 1 }
	 * 从而可以使用动态规划。
	 * 
	 * answer	: 14489159
	 * time cost: 11282 ms
	 * @param args
	 */
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		
		int m = 1000000;
		int[] mdrs = new int[m];
		mdrs[0] = 0;
		mdrs[1] = 0;
		for (int i = 2; i < mdrs.length; i ++) {
			int max = -1;
//			System.out.println("======" + i);
			for (int j = 2; j*j <= i; j ++) {
				if (i % j == 0) {
					int a = (mdrs[j] == -1)?drs(j):Math.max(drs(j), mdrs[j]);
					int b = (mdrs[i/j] == -1)?drs(i/j):Math.max(drs(i/j), mdrs[i/j]);
					int t = a + b;
//					System.out.println("mdrs(" + j + ") + mdrs(" + (i/j) + ") = " + t);
					if (max == -1 || t > max) {
						max = t;
					}
				}
			}
			mdrs[i] = Math.max(drs(i), max);
		}
		
		long sum = 0;
		for (int i = 2; i < m; i ++) {
			sum += mdrs[i];
		}
		System.out.println(sum);

		System.out.println((System.currentTimeMillis()-start) + " ms");
	}

	private static int drs(int i) {

		return (i%9 == 0)? 9:i%9; 
	}
}
